import java.util.Arrays;

public class HashBucket<K, V> {
    public double loadFactor = 0.75;
    public int usedSize = 0;
    public Node<K, V>[] array = (Node<K, V>[])new Node[10];
    static class Node<K, V>{
        public K key;
        public V val;
        public Node<K, V> next;
        public Node(K key, V val) {
            this.key = key;
            this.val = val;
        }
    }
    public void put(K key, V val){
        Node<K, V> node = new Node<>(key, val);
        int k = key.hashCode();
        int index = k % array.length;
        Node<K, V> cur = array[index];
        if(cur == null){
            array[index] = node;
            usedSize++;
            return ;
        }
        else{
            if(cur.key.equals(key)){
                cur.val = val;
                usedSize++;
                return ;
            }
        }
        while(cur.next != null){
            if(cur.key.equals(key)){
                cur.val = val;
                return ;
            }
            cur = cur.next;
        }
        cur.next = node;
        usedSize++;
        if(loadFactor() >= loadFactor){
            enlargeCapacity();
        }
    }
    private double loadFactor(){
        return usedSize*1.0 / array.length;
    }
    private void enlargeCapacity(){
        array = Arrays.copyOf(array, array.length*2);
        for(int i = 0; i < array.length/2; i++){
            Node<K, V> cur = array[i];
            while(cur != null){
                int k = cur.key.hashCode() % array.length;
                if(k != i){
                    Node<K, V> node = cur;
                    cur = cur.next;
                    array[i] = cur;
                }
                else{
                    cur = cur.next;
                    break;
                }
            }
            Node<K, V> curN = array[i];
            while(cur != null){
                int k = cur.key.hashCode() % array.length;
                if(k != i){
                    Node<K, V> node = cur;
                    curN.next = cur.next;
                    cur = curN.next;
                    Node<K, V> target = array[k];
                    if(target == null){
                        array[k] = node;
                    }
                    else {
                        while (target.next != null) {
                            target = target.next;
                        }
                        target.next = node;
                    }
                }
                else{
                    cur = cur.next;
                }
            }
        }
    }
    public V get(K key){
        int k = key.hashCode();
        int index = k % array.length;
        Node<K, V> cur = array[index];
        while(cur != null){
            if(cur.key.equals(key)){
                return cur.val;
            }
            cur = cur.next;
        }
        return null;
    }
}
